1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
|
1
2 树状数组，具体的说是 离散化+树状数组。这也是学习树状数组的第一题.
3 算法的大体流程就是：
4 1.先对输入的数组离散化，使得各个元素比较接近，而不是离散的，
5 2.接着，运用树状数组的标准操作来累计数组的逆序数。
6 算法详细解释：
7 1.解释为什么要有离散的这么一个过程？//为了后面用树状数组
8 刚开始以为999.999.999这么一个数字，对于int存储类型来说是足够了。
9 还有只有500000个数字，何必要离散化呢？
10 刚开始一直想不通，后来明白了，后面在运用树状数组操作的时候，
11 用到的树状数组C[i]是建立在一个有点像位存储的数组的基础之上的，
12 不是单纯的建立在输入数组之上。
13 比如输入一个9 1 0 5 4，那么C[i]树状数组的建立是在，
14
15 数据：9 1 0 5 4 p[i].val
16 编号：1 2 3 4 5 p[i].oder = i*************
17 sort
18 数据：0 1 4 5 9
19 编号：3 2 5 4 1
20 顺序：1 2 3 4 5
21
22 a[p[i].编号] = 顺序号;**********************
23
24 a[3] = 1<--0;
25 a[2] = 2<--1;
26 a[5] = 3<--4;
27 a[4] = 4<--5;
28 a[1] = 5<--9;
29
30 a[]={ 5 2 1 4 3 }
31
32 新号：1 2 3 4 5
33 值 ：
34
35
36 下标 0 1 2 3 4 5 6 7 8 9
37 数组 1 1 0 0 1 1 0 0 0 1
38 现在由于999999999这个数字相对于500000这个数字来说是很大的，
39 所以如果用数组位存储的话，那么需要999999999的空间来存储输入的数据。
40 这样是很浪费空间的，题目也是不允许的，所以这里想通过离散化操作，
41 使得离散化的结果可以更加的密集。
42 2. 怎么对这个输入的数组进行离散操作？
43 离散化是一种常用的技巧，有时数据范围太大，可以用来放缩到我们能处理的范围；
44 因为其中需排序的数的范围0---999 999 999；显然数组不肯能这么大；
45 而N的最大范围是500 000；故给出的数一定可以与1.。。。N建立一个一一映射；
46 ①当然用map可以建立，效率可能低点；
47 ②这里用一个结构体
48 struct Node
49 {
50 int v,ord;
51 }p[510000];和一个数组a[510000];
52
53 其中v就是原输入的值，ord是下标；
54 然后对结构体按v从小到大排序；
55
56 此时，v和结构体的下标就是一个一一对应关系，
57 而且满足原来的大小关系；
58
59 for(i=1;i<=N;i++)
60 a[p[i].ord]=i;
61
62 然后a数组就存储了原来所有的大小信息；
63 比如 9 1 0 5 4 ------- 离散后aa数组
64 就是 5 2 1 4 3；
65 具体的过程可以自己用笔写写就好了。
66 3. 离散之后，怎么使用离散后的结果数组来进行树状数组操作，计算出逆序数？
67 如果数据不是很大， 可以一个个插入到树状数组中，
68 每插入一个数， 统计比他小的数的个数，
69 对应的逆序为 i- getsum( aa[i] ),
70 其中 i 为当前已经插入的数的个数，
71 getsum( aa[i] ）为比 aa[i] 小的数的个数,
72 i- sum( aa[i] ) 即比 aa[i] 大的个数， 即逆序的个数
73 但如果数据比较大，就必须采用离散化方法
74 假设输入的数组是9 1 0 5 4， 离散后的结果aa[] = {5,2,1,4,3};
75 在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。
76 1，输入5， 调用upDate(5, 1),把第5位设置为1
77 1 2 3 4 5
78 0 0 0 0 1
//后面都是计算1-n上小于等于n的数的总数,而不是小于n的数的总数,是考虑了重复的情况
79 计算1-5上比5小(小于等于5)的数字存在么？ 这里用到了树状数组的getSum（5） = 1操作，
80 现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。
81 2. 输入2， 调用upDate(2, 1),把第2位设置为1
82 1 2 3 4 5
83 0 1 0 0 1
84 计算1-2上比2小(小于等于2)的数字存在么？ 这里用到了树状数组的getSum（2） = 1操作，
85 现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。
86 3. 输入1， 调用upDate(1, 1),把第1位设置为1
87 1 2 3 4 5
88 1 1 0 0 1
89 计算1-1上比1小(小于等于1)的数字存在么？ 这里用到了树状数组的getSum（1） = 1操作，
90 现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。
91 4. 输入4， 调用upDate(4, 1),把第4位设置为1
92 1 2 3 4 5
93 1 1 0 1 1
94 计算1-4上比4小(小于等于1)的数字存在么？ 这里用到了树状数组的getSum（4） = 3操作，
95 现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。
96 5. 输入3， 调用upDate(3, 1),把第3位设置为1
97 1 2 3 4 5
98 1 1 1 1 1
99 计算1-3上比3小(小于等于3)的数字存在么？ 这里用到了树状数组的getSum（3） = 3操作，
100 现在用输入的下标5 - getSum(3) = 2 就可以得到对于3的逆序数为2。
101 6. 0+1+2+1+2 = 6 这就是最后的逆序数
102 分析一下时间复杂度，首先用到快速排序，时间复杂度为O(NlogN),
103 后面是循环插入每一个数字，每次插入一个数字，分别调用一次upData()和getSum()
104 外循环N, upData()和getSum()时间O(logN) => 时间复杂度还是O(NlogN).
105 */
代码：
版本一：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 500005;
struct Node{
int val;
int pos;
};
Node node[N];
int n;
int tree[N], reflect[N];
bool cmp(const Node &a, const Node &b)
{
return a.val < b.val;
}
int lowbit(int x)
{
return x & -x;
}
void update(int index, int val)
{
while(index <= n){
tree[index] += val;
index += lowbit(index);
}
}
int getsum(int index)
{
int sum = 0;
while(index > 0){
sum += tree[index];
index -= lowbit(index);
}
return sum;
}
int main()
{
while(scanf("%d", &n) != EOF && n){
for(int i = 1; i <= n; i++){
scanf("%d", &node[i].val);
node[i].pos = i;
}
sort(node + 1, node + 1 + n, cmp);
for(int i = 1; i <= n; i++){
reflect[node[i].pos] = i;
}
for(int i = 1; i <= n; i++)
tree[i] = 0;
long long ans = 0;
for(int i = 1; i <= n; i++){
update(reflect[i], 1);
ans += i - getsum(reflect[i]);
}
printf("%lld\n", ans);
}
return 0;
}
版本二：
离散化借助了两个数组，需要用二分查找
1. #include<cstdio>
2. #include<cstring>
3. #include<iostream>
4. #include<algorithm>
5. using namespace std;
6.
7. const int MAXN = 500010;
8.
9. int n;
10. int tmpNum[MAXN] , num[MAXN];
11. int treeNum[MAXN];
12.
13. int lowbit(int x){
14. return x&(-x);
15. }
16.
17. int getSum(int x){
18. int sum = 0;
19. while(x){
20. sum += treeNum[x];
21. x -= lowbit(x);
22. }
23. return sum;
24. }
25.
26. void add(int x , int val){
27. while(x < MAXN){
28. treeNum[x] += val;
29. x += lowbit(x);
30. }
31. }
32.
33. int search(int x , int len){
34. int left = 1;
35. int right = len;
36. while(left <= right){
37. int mid = (left+right)>>1;
38. if(num[mid] == x)
39. return mid;
40. else if(num[mid] < x)
41. left = mid+1;
42. else
43. right = mid-1;
44. }
45. }
46.
47. long long solve(){
48. long long ans = 0;
49. memcpy(tmpNum , num , sizeof(num));
50. memset(treeNum , 0 , sizeof(treeNum));
51. sort(num+1 , num+1+n);
52. int len = unique(num+1 , num+1+n)-(num+1);
53. for(int i = 1 ; i <= n ; i++){
54. int id = search(tmpNum[i] , len);
55. ans += i-getSum(id)-1;
56. add(id , 1);
57. }
58. return ans;
59. }
60.
61. int main(){
62. while(scanf("%d" , &n) && n){
63. for(int i = 1 ; i <= n ; i++)
64. scanf("%d" , &num[i]);
65. printf("%lld\n" , solve());
66. }
67. return 0;
68. }
|
